(function () {
    function SearchCursor(cm, query, pos, caseFold) {
        this.atOccurrence = false;
        this.cm = cm;
        if (caseFold == null && typeof query == "string") caseFold = false;

        pos = pos ? cm.clipPos(pos) : {line: 0, ch: 0};
        this.pos = {from: pos, to: pos};

        // The matches method is filled in based on the type of query.
        // It takes a position and a direction, and returns an object
        // describing the next occurrence of the query, or null if no
        // more matches were found.
        if (typeof query != "string") { // Regexp match
            if (!query.global) query = new RegExp(query.source, query.ignoreCase ? "ig" : "g");
            this.matches = function (reverse, pos) {
                if (reverse) {
                    query.lastIndex = 0;
                    var line = cm.getLine(pos.line).slice(0, pos.ch), match = query.exec(line), start = 0;
                    while (match) {
                        start += match.index + 1;
                        line = line.slice(start);
                        query.lastIndex = 0;
                        var newmatch = query.exec(line);
                        if (newmatch) match = newmatch;
                        else break;
                    }
                    start--;
                } else {
                    query.lastIndex = pos.ch;
                    var line = cm.getLine(pos.line), match = query.exec(line),
                        start = match && match.index;
                }
                if (match)
                    return {
                        from: {line: pos.line, ch: start},
                        to: {line: pos.line, ch: start + match[0].length},
                        match: match
                    };
            };
        } else { // String query
            if (caseFold) query = query.toLowerCase();
            var fold = caseFold ? function (str) {
                return str.toLowerCase();
            } : function (str) {
                return str;
            };
            var target = query.split("\n");
            // Different methods for single-line and multi-line queries
            if (target.length == 1)
                this.matches = function (reverse, pos) {
                    var line = fold(cm.getLine(pos.line)), len = query.length, match;
                    if (reverse ? (pos.ch >= len && (match = line.lastIndexOf(query, pos.ch - len)) != -1)
                            : (match = line.indexOf(query, pos.ch)) != -1)
                        return {
                            from: {line: pos.line, ch: match},
                            to: {line: pos.line, ch: match + len}
                        };
                };
            else
                this.matches = function (reverse, pos) {
                    var ln = pos.line, idx = (reverse ? target.length - 1 : 0), match = target[idx], line = fold(cm.getLine(ln));
                    var offsetA = (reverse ? line.indexOf(match) + match.length : line.lastIndexOf(match));
                    if (reverse ? offsetA >= pos.ch || offsetA != match.length
                            : offsetA <= pos.ch || offsetA != line.length - match.length)
                        return;
                    for (; ;) {
                        if (reverse ? !ln : ln == cm.lineCount() - 1) return;
                        line = fold(cm.getLine(ln += reverse ? -1 : 1));
                        match = target[reverse ? --idx : ++idx];
                        if (idx > 0 && idx < target.length - 1) {
                            if (line != match) return;
                            else continue;
                        }
                        var offsetB = (reverse ? line.lastIndexOf(match) : line.indexOf(match) + match.length);
                        if (reverse ? offsetB != line.length - match.length : offsetB != match.length)
                            return;
                        var start = {line: pos.line, ch: offsetA}, end = {line: ln, ch: offsetB};
                        return {from: reverse ? end : start, to: reverse ? start : end};
                    }
                };
        }
    }

    SearchCursor.prototype = {
        findNext: function () {
            return this.find(false);
        },
        findPrevious: function () {
            return this.find(true);
        },

        find: function (reverse) {
            var self = this, pos = this.cm.clipPos(reverse ? this.pos.from : this.pos.to);

            function savePosAndFail(line) {
                var pos = {line: line, ch: 0};
                self.pos = {from: pos, to: pos};
                self.atOccurrence = false;
                return false;
            }

            for (; ;) {
                if (this.pos = this.matches(reverse, pos)) {
                    this.atOccurrence = true;
                    return this.pos.match || true;
                }
                if (reverse) {
                    if (!pos.line) return savePosAndFail(0);
                    pos = {line: pos.line - 1, ch: this.cm.getLine(pos.line - 1).length};
                }
                else {
                    var maxLine = this.cm.lineCount();
                    if (pos.line == maxLine - 1) return savePosAndFail(maxLine);
                    pos = {line: pos.line + 1, ch: 0};
                }
            }
        },

        from: function () {
            if (this.atOccurrence) return this.pos.from;
        },
        to: function () {
            if (this.atOccurrence) return this.pos.to;
        },

        replace: function (newText) {
            var self = this;
            if (this.atOccurrence)
                self.pos.to = this.cm.replaceRange(newText, self.pos.from, self.pos.to);
        }
    };

    CodeMirror.defineExtension("getSearchCursor", function (query, pos, caseFold) {
        return new SearchCursor(this, query, pos, caseFold);
    });
})();
